package com.my.study.structures.sort;

import java.util.Arrays;

/**
 * @author Carlos
 * @version 1.0
 * @Description 插入排序
 * 基本思想：
 * 将数据集分为两个区，前面为排序好的区，后面为乱序
 *
 * @date 2021/7/15 22:23
 **/
public class InsertSort {

    public static void main(String[] args) {

        int[] arr = {101, 34, 119, 1};
        sort(arr);

        System.out.println(Arrays.toString(arr));

    }


    private static void sort(int[] arr) {
        int insertVal = 0;
        int insertIndex = 0;
        for (int i = 1; i < arr.length; i++) {
            insertVal = arr[i];
            insertIndex = i - 1;
            // 降序insertVal > arr[insertIndex]
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            if (insertIndex + 1 != i) {
                arr[insertIndex + 1] = insertVal;
            }
        }


        /*// 第一轮 {101, 34, 119, 1} => {34, 101, 119, 1}
        // 定义待插入的数
        int insertVal = arr[1];
        // 即arr[1]的前面这个数的下标
        int insertIndex = 1 - 1;

        // 给insertVal找到插入的位置
        // 说明：
        // 1.insertIndex >= 0保证在给 insertIndex 找插入位置，不越界
        // 2.insertVal < arr[insertIndex]，待插入的数还没找到插入位置
        // 3.就需要将arr[insertIndex]后移
        while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
            arr[insertIndex+1] = arr[insertIndex];
            insertIndex--;
        }

        // 退出循环时，说明插入位置找到，insertIndex + 1
        arr[insertIndex+1] = insertVal;

        System.out.println("第1轮");
        System.out.println(Arrays.toString(arr));

        //=========================
        insertVal = arr[2];
        // 即arr[1]的前面这个数的下标
        insertIndex = 2 - 1;
        while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
            arr[insertIndex+1] = arr[insertIndex];
            insertIndex--;
        }
        arr[insertIndex+1] = insertVal;

        System.out.println("第1轮");
        System.out.println(Arrays.toString(arr));*/


    }

}
